This invention relates to a method of accelerating operations in a finite field, and in particular, to operations performed in a field F2m such as used in encryption systems.
Finite fields of characteristic two in F2m are of interest since they allow for the efficient implementation of elliptic curve arithmetic. The field F2m can be viewed as a vector space of dimension m over F2. Once a basis of F2m over F2 has been chosen the elements of F2m can be conveniently represented as vectors of elements zero or one and of length m. In hardware, a field element is stored in a shift register of length m. Addition of field elements is performed by bitwise XOR-ing (⊕) the vector representations and takes one clock cycle.
Digital signatures are used to confirm that a particular party has sent a message and that the contents have not been altered during transmission.
A widely used set of signature protocols utilizes the ElGamal public key signature scheme that signs a message with the sender""s private key. The recipient may then verify the signature with the sender""s public key.
Various protocols exist for implementing such a scheme and some have been widely used. In each case however the recipient is required to perform a computation to verify the signature. Where the recipient has adequate computing power this does not present a particular problem but where the recipient has limited computing power, such as in a xe2x80x9cSmart cardxe2x80x9d application, the computations may introduce delays in the verification process. Public key schemes may be implemented using one of a number of groups in which the discrete log problem appears intractable but a particularly robust implementation is that utilizing the characteristics of points on an elliptic curve over a finite field. This implementation has the advantage that the requisite security can be obtained with relatively small orders of field compared with for example with implementations in Zpxe2x86x92 and therefore reduces the bandwidth required for communicating the signatures.
In a typical implementation a signature component s has the form:
s=ae+k (mod n)
where:
P is a point on the curve, which is predefined parameter of the system;
k is a random integer selected as a short term private or session key, and has a corresponding short term public key R=kP;
a is the long term private key of the sender and has a corresponding public key aP=Q;
e is a secure hash, such as the SHA hash function, of a message m and short term public key R; and
n is the order of the curve.
The sender sends to the recipient a message including m, s, and R and the signature is verified by computing th value Rxe2x80x2=(sPxe2x88x92cQ) which should correspond to R. If the computed values are equivalent then the signature is verified.
In order to perform the verification it is necessary to compute a number of point multiplications to obtain sP and eQ, each of which is computationally complex.
If Fq is a finite field, the elliptic curves over Fq can be divided into two classes, namely supersingular and non-supersingular curves. If Fq is of characteristic 2, i.e. q=2M, then the classes are defined as follows.
i) The set of all solutions to the equation y2+ay=x3+bx+c where a,b,cxcex5Fq, axe2x89xa00, together with a special point called the point at infinity O is a supersingular curve over Fq.
ii) The set of all solutions to the equation y2+xy=x3ax2+b where a,bxcex5Fq, bxe2x89xa00, together with a special pointed called the point at infinity O is a nonsupersingular curve over Fq.
By defining an appropriate addition on these points, we obtain an additive abelian group. The addition of two points P(x1,y1) and Q(x2,y2) for the supersingular elliptic curve E with y2+ayxe2x88x92x3+bxxe2x88x92c is given by the following:
If P(x1,y1)xe2x8ax96E; then define xe2x88x92P=(x1,y1+a),P+O=O+P=P for all Pxcex5E.
If Q=(x2,y2)xe2x8ax96E and Qxe2x89xa0xe2x88x92P, then the point representing the sum of P+Q, is denoted (x3,y3), where                               x          3                =                  {                                                    (                                                                            y                      1                                        ⊕                                          y                      2                                                                                                  x                      1                                        ⊕                                          x                      2                                                                      )                            2                        ⊕                          x              1                        ⊕                          x              2                                                                    (                      T            ≠            Q                    )                ⁢                  xe2x80x83                ⁢        or                                          x          3                =                  {                                                    x                1                2                            ⊕                              b                7                                                    a              2                                                                    (                      P            =            Q                    )                ⁢                  xe2x80x83                ⁢        and                                          y          3                =                  {                                    (                                                                    y                    1                                    ⊕                                      y                    2                                                                                        x                    1                                    ⊕                                      x                    2                                                              )                        ⊕                          (                                                x                  1                                ⊕                                  x                  3                                            )                        ⊕                          y              1                        ⊕            a                                                        (                      P            ≠            Q                    )                ⁢                  xe2x80x83                ⁢        or                                          y          3                =                  {                                    (                                                                    x                    1                    2                                    ⊕                  b                                a                            )                        ⊕                          (                                                x                  1                                ⊕                                  x                  3                                            )                        ⊕                          y              1                        ⊕            a                                              (                  P          -          Q                )            
The addition of two points P(x1,y1) and Q(x2,y2) for the nonsupersingular elliptic curve y3+xy=x3+ax3+b is given by following:
If P=(x1,y1)xcex5E then define xe2x88x92P=(x1,y1+x1). For all Pxcex5E, O+P=P+O=P. If Q=(x2,y2)⊂E and Qxe2x89xa0xe2x88x92P, then P+Q is a point (x3,y3), where                               x          3                =                  {                                                    (                                                                            y                      1                                        ⊕                                          y                      2                                                                                                  x                      1                                        ⊕                                          x                      2                                                                      )                            2                        ⊕                                                            y                  1                                ⊕                                  y                  2                                                                              x                  1                                ⊕                                  x                  2                                                      ⊕                          x              1                        ⊕                                          x                2                            ⁢              a                                                                    (                      P            ≠            Q                    )                ⁢                  xe2x80x83                ⁢        or                                          x          3                =                  {                                    x              1              2                        ⊕                          b                              x                1                2                                                                                              (                          P              =              Q                        )                    ]                ⁢                  xe2x80x83                ⁢        and                                          y          3                =                  {                                    (                                                                    y                    1                                    ⊕                                      y                    2                                                                                        x                    1                                    ⊕                                      x                    2                                                              )                        ⊕                          (                                                x                  1                                ⊕                                  x                  3                                            )                        ⊕                          x              3                        ⊕                          y              1                                                                    (                      P            ≠            Q                    )                ⁢                  xe2x80x83                ⁢        or                                          y          3                =                  {                                                    x                1                2                            ⁡                              (                                                      x                    1                                    ⊕                                                            y                      1                                                              x                      1                                                                      )                                      ⊕                          x              1                        ⊕                          x              3                                                          (                  P          =          Q                )            
Now supersingular curves are preferred, as they are more resistant to the MOV attack. It can be seen that computing the sum of two points on E requires several multiplications, additions, and inverses in the underlying field F2m. In turn, each of these operations requires a sequence of elementary bit operations.
When implementing cryptographic operations in ElGamal or Diffie-Hellman schemes or generally most cryptographic operations with elliptic curves, one is required to compute kP=P+P+ . . . +P (P added k times) where k is a positive integer and Pxcex5E. This requires the computation of (x3,y3) to be computed kxe2x88x921 times. For large values of k which are typically necessary in cryptographic applications, this has previously been considered impractical for data communication. If k is large, for example 1024 bits, kP would be calculated by performing 21024 additions of P.
Furthermore, in a multiplicative group, multiplications and inversions are extremely computationally intensive, with field inversions being more expensive than field multiplications. The inversion operation needed when adding two points can be eliminated by resorting to projective coordinates. The formula for addition of two points however, requires a larger number of multiplications than is required when using affine coordinates.
In a paper entitled xe2x80x9cElliptic Curve Cryptosystems and Their Implementationxe2x80x9d by Vanstone et al., published in The Journal of Cryptology, a method is described for adding two points by converting to projective coordinates and thus eliminating the inversion computation. However the overall gain in speed by elimination of the inversion is at the expense of space. Extra registers are required to store P and Q and also to store intermediate results when doing the addition. Furthermore, this method requires the use of the y-coordinate in the calculation.
It is therefore an object of the present invention to provide a method and apparatus in which some of the above disadvantages are obviated or mitigated.
It is a further object of the invention to provide a method of multiplying finite field elements, and which may be implemented relatively efficiently on a processor with limited processing capability, such as a smart card or the like.
It is a still further object of the present invention to provide a method and apparatus in which signature verification may be accelerated in elliptic curve encryption systems.
In accordance with this invention there is provided a method of determining a multiple of a point P on an elliptic curve defined over a field F2M, said method comprising steps of:
a) representing the number k as a vector of binary digits ki;
b) forming a pair of points P1 and P2, wherein the point P1 and P2 differ at most by P; and
c) selecting each of the ki in turn and for each of the kl,
upon the ki being a one, adding the pair of points P1 and P2 to form a new point P1 and adding the point P to P1 to form a new point P2, the new points replacing the pair of points P1 and P2; or
upon the ki being a zero, doubling the point P1 to form a new point P1 and adding the point P to form a new point P2, the new points replacing the pair of points P1 and P2, whereby the product kP is obtained from the point P1 in Mxe2x88x921 steps and wherein M represents the number of digits in k.
Furthermore, the inventors have implemented a method whereby computation of a product kP can be performed without the use of the y coordinate of the point P during computation.